#include <iostream>
#include <string.h>
#include <vector>
#include <map>
#include <string>
#include <stdbool.h>
#include <queue>
#include "UnionFindSet.hpp"
using namespace std;

namespace matrix
{
    template<class V,class W,bool G=false>
    class Graph
    {
        private:
            vector<V> _vertexs;
            map<V,int> _indexMap;
            vector<vector<W>> _matrix;

        public:

            Graph()=default;

            Graph(const V* arr,size_t n)
            {
                _vertexs.resize(n);

                for(size_t i=0;i<n;i++)
                {
                    _vertexs[i]=arr[i];
                    _indexMap[arr[i]]=i;
                }

                _matrix.resize(n);

                for(size_t i=0;i<n;i++)
                {
                    _matrix[i].resize(n,INT32_MAX);
                }
            }

           size_t GetVertexIndex(const V& v)
           {
               auto it=_indexMap.find(v);
               if(it!=_indexMap.end())
               {
                   return it->second;
               }
               else 
               {
                   perror("_indexMap.find()");
                   return -1;
               }
           }

            void AddEdge(const V& src,const V& dst,const W& w)
            {
                size_t srci=GetVertexIndex(src);
                size_t dsti=GetVertexIndex(dst);

                _matrix[srci][dsti]=w;
                if(G==false)
                {
                    _matrix[dsti][srci]=w;
                }

            }
          
            void AddEdge(size_t srci,size_t dsti,const W& w)
            {

                _matrix[srci][dsti]=w;
                if(G==false)
                {
                    _matrix[dsti][srci]=w;
                }

            }
            void _BFS(size_t index,vector<bool>& visit)
            {
               queue<size_t> q;

                q.push(index); // 先将index下标对应的顶点入队
                visit[index]=true; // 再记录index对应的顶点被访问过

                while(!q.empty())
                {
                    size_t front=q.front();
                    q.pop();

                    cout<<_vertexs[front]<<endl;

                    size_t n=_matrix[front].size();

                    for(size_t i=0;i<n;i++)
                    {
                        if(_matrix[front][i]!=INT32_MAX && visit[i]==false)
                        {
                            // 如果与顶点front相邻并且没有被访问过，则将该顶点入队
                            q.push(i);
                            visit[i]=true;
                        }
                    }
                }

            }

            // 图的遍历---广度优先遍历
            void BFS(const V& src)
            {
                // 记录顶底是否被访问过
                vector<bool> visit(_vertexs.size(),false);
                
                size_t srci=GetVertexIndex(src);

                _BFS(srci,visit);
               //for(size_t i=0;i<visit.size();i++)
               // {
               //     if(visit[i]==false)
               //     {
               //         _BFS(i,visit);
               //     }
               // }

            }
            

            void _DFS(size_t index,vector<bool>& visit)
            {
                size_t n=_matrix[index].size();

                cout<<_vertexs[index]<<endl;

                visit[index]=true;

                for(size_t i=0;i<n;i++)
                {
                    if(_matrix[index][i]!=INT32_MAX && visit[i]==false)
                    {
                        _DFS(i,visit);
                    }
                }

            }

            // 图的深度优先遍历
            void DFS(const V& src)
            {
                vector<bool> visit(_vertexs.size(),false);

                size_t srci=GetVertexIndex(src);

                _DFS(srci,visit);

                for(size_t i=0;i<visit.size();i++)
                {
                    if(visit[i]==false)
                    {
                        _DFS(i,visit);
                    }
                }

            }

            //void Print()
            //{
            //    for(int i=0;i<_vertexs.size();i++)
            //    {
            //        cout<<_vertexs[i]<<endl;
            //    }
            //}
            
            
            template<typename TW>
            struct Edge 
            {
                size_t _srci;
                size_t _dsti;
                TW _w;

                Edge(size_t srci,size_t dsti,const TW& w)
                    :_srci(srci)
                    ,_dsti(dsti)
                    ,_w(w)
                {

                }

                bool operator>(const Edge<TW>& e) const
                {
                    return _w>e._w;
                }

            };

            // 最小生成树算法
            // kruskal（克鲁斯卡尔）
           W kruskal(Graph<V,W>& minTree)
           {
                minTree._vertexs=_vertexs;
                minTree._indexMap=_indexMap;
                minTree._matrix.resize(_matrix.size());
                for(size_t i=0;i<_matrix.size();i++)
                {
                    minTree._matrix[i].resize(_matrix.size(),INT32_MAX);
                }
                
               priority_queue<Edge<W>,vector<Edge<W>>,greater<Edge<W>>> pq;

               for(size_t i=0;i<_matrix.size();i++)
               {
                   for(size_t j=0;j<_matrix[i].size();j++)
                   {
                       if(i<j&&_matrix[i][j]!=INT32_MAX)
                       {
                           pq.push(Edge<W>(i,j,_matrix[i][j]));
                       }
                   }
               }
               
               size_t size=0;

               UnionFindSet ufs(_vertexs.size());

               W min=0;

               while(!pq.empty())
               {
                    Edge<W> front=pq.top();
                    pq.pop();

                    if(ufs.InSet(front._srci,front._dsti))
                    {
                        
                        minTree.AddEdge(front._srci,front._dsti,front._w);
                        min+=front._w;
                        ufs.Union(front._srci,front._dsti);
                        size++;
                        if(size==_vertexs.size()-1)
                        {
                            break;
                        }
                    }
                    
                
               }

               if(size==_vertexs.size()-1)
               {
                   return min;
               }
               else 
               {
                   return W();
               }
           }
        
           // 最小生成树---普里姆（prim）
           W Prim(Graph<V,W>& minTree)
           {
                size_t n=_matrix.size();
                minTree._vertexs=_vertexs;
                minTree._indexMap=_indexMap;
                minTree._matrix.resize(n);

                for(size_t i=0;i<n;i++)
                {
                    minTree._matrix[i].resize(n,INT32_MAX);
                }
                
                vector<bool> X(n,false);
                //vector<bool> Y(n,false);

                size_t srci=0;
                X[srci]=true;

                priority_queue<Edge<W>,vector<Edge<W>>,greater<Edge<W>>> pq;
                
                for(size_t i=0;i<n;i++)
                {
                    if(_matrix[srci][i]!=INT32_MAX)
                    {
                        pq.push(Edge<W>(srci,i,_matrix[srci][i]));
                    }
                }

                size_t size=0;
                W min=0;

                while(!pq.empty())
                {
                    Edge<W> front=pq.top();
                    pq.pop();
                    
                    if(X[front._dsti]==false)
                    {
                        minTree.AddEdge(front._srci,front._dsti,front._w);
                        X[front._dsti]=true;
                        for(size_t i=0;i<n;i++)
                        {
                            if(_matrix[front._dsti][i]!=INT32_MAX)
                            {
                                pq.push(Edge<W>(front._dsti,i,_matrix[front._dsti][i]));
                            }
                        }

                        size++;
                        min+=front._w;
                        if(size==n-1)
                        {
                            break;
                        }
                    }
                    

                }
                if(size==n-1)
                {
                    return min;
                }
                return W();

           }

    };

    void TestGraph()
    {
       // int arr[]={1,3,5,7,9};

       // Graph<int,int> g(arr,5);

       // g.Print();
      // int arr[]={1,3,5,7,9,11,13,15,17,19};
      //  
      // Graph<int,int> g(arr,sizeof(arr)/sizeof(arr[0]));

      // g.AddEdge(1,3,1);
      // g.AddEdge(1,5,2);
      // g.AddEdge(1,13,2);
      // g.AddEdge(1,7,3);
      // g.AddEdge(13,11,4);
      // g.AddEdge(5,15,5);
      // g.AddEdge(5,17,9);
      // g.AddEdge(5,19,1);
      // g.AddEdge(7,9,10);
      // g.AddEdge(11,9,7);

      // //g.DFS(1);

      // Graph<int,int> minTree;
      // g.kruskal(minTree);

      // minTree.BFS(1);
      const char* str="abcdefghi";
      Graph<char,int> g(str,strlen(str));

      g.AddEdge('a','b',4);
      g.AddEdge('a','h',8);
      g.AddEdge('b','c',8);
      g.AddEdge('b','h',11);
      g.AddEdge('c','i',2);
      g.AddEdge('c','f',4);
      g.AddEdge('c','d',7);
      g.AddEdge('d','f',14);
      g.AddEdge('d','e',9);
      g.AddEdge('e','f',10);
      g.AddEdge('f','g',2);
      g.AddEdge('g','h',1);
      g.AddEdge('g','i',6);
      g.AddEdge('h','i',7);
      //g.AddEdge('a','b',4);
      //g.BFS('a');
      //cout<<endl;
      //g.DFS('a');
      Graph<char,int> min;
      cout<<g.Prim(min)<<endl;
      min.BFS('a');
      cout<<endl;
      min.DFS('a');



    }
};

namespace linkTable
{

    template<class W>
    struct Edge 
    {
        int _dst;
        Edge<W>* _next;
        W _w;

        Edge(int dst,const W& w)
            :_dst(dst)
            ,_next(nullptr)
            ,_w(w)
        {

        }
    };

    template<class V,class W,bool G>
    class Graph 
    {
        typedef Edge<W> edge;

      private:
          vector<V> _vertexs;
          map<V,int> _indexMap;
          vector<edge*> _table;

    public:
          Graph(const V* arr,size_t n)
          {
              _vertexs.resize(n);
              for(size_t i=0;i<n;i++)
              {
                  _vertexs[i]=arr[i];
                  _indexMap[arr[i]]=i;
              }

              _table.resize(n,nullptr);
          }


        size_t GetIndex(const V& v)
        {
            auto it=_indexMap.find(v);
            if(it!=_indexMap.end())
            {
                return it.second;
            }
            else 
            {
                return -1;
            }
        }

          void AddEdge(const V& src,const V& dst,const W& w)
          {
              size_t srci=GetIndex(src);
              size_t dsti=GetIndex(dst);

              edge* newEdge=new edge(dsti,w);
              newEdge->_next=_vertexs[srci];
              _vertexs[srci]=newEdge;
              if(G==false)
              {
                edge* newEdge=new edge(srci,w);
                newEdge->_next=_vertexs[dsti];
                _vertexs[dsti]=newEdge;

              }
          }

    };
};






